﻿#include <iostream>
#include <assert.h>

typedef enum : unsigned char
{
	// 连通区右扩
	LOOP_STATE_ANTICLOCKWISE,
	// 连通区左扩
	LOOP_STATE_CLOCKWISE,
	// 找到了一个良好出发点，左扩看这个点之前的能否到达这个点
	LOOP_STATE_FOUND_START_CLOCKWISE,
}LOOP_STATE;

static bool* judgeSuitableStart(int* oil, int* dis, size_t size)
{
	bool* res = (bool*)malloc(size * sizeof(bool));
	memset(res, 0, size * sizeof(bool));

	// 将oil变为纯能值数组
	for (int i = 0; i < size; i++)
	{
		oil[i] = oil[i] - dis[i];
	}

	// 处理过的点的数量
	int finishedCount = 0;

	// 选一个大于0的点作为起始点
	int startIndex = -1;
	for (int i = 0; i < size; i++)
	{
		if (oil[i] > 0)
		{
			startIndex = i;
			break;
		}
	}

	// 如果没有>0的点，直接返回
	if (startIndex == -1) return res;

	int left = startIndex;
	int nextLeft;
	int last = size - 1;
	int right = (startIndex == last) ? 0 : (startIndex + 1);
	int need = 0;
	int rest = oil[startIndex];
	// 已经找到的最后一个良好出发点
	int foundSuitableStart = -1;
	LOOP_STATE state = LOOP_STATE_ANTICLOCKWISE;

	while (finishedCount < size)
	{
		switch (state)
		{
		case LOOP_STATE_ANTICLOCKWISE:
			if (rest + oil[right] >= 0)
			{
				rest += oil[right];
				right = (right == last) ? 0 : (right + 1);
				if (right == left)
				{
					res[left] = true;
					++finishedCount;
					foundSuitableStart = left;
					left = (left == 0) ? last : (left - 1);
					need = 0;
					state = LOOP_STATE_FOUND_START_CLOCKWISE;
				}
			}
			else
			{
				left = (left == 0) ? last : (left - 1);
				state = LOOP_STATE_CLOCKWISE;
			}

			break;

		case LOOP_STATE_CLOCKWISE:
			rest += oil[left];
			if (oil[left] - need >= 0)
			{
				state = LOOP_STATE_ANTICLOCKWISE;
			}
			else
			{
				++finishedCount;
				nextLeft = (left == last) ? 0 : (left + 1);
				if (oil[left] < 0)
				{
					need -= oil[left] + oil[nextLeft];
				}

				if (need < 0)
				{
					need = 0;
				}

				left = (left == 0) ? last : (left - 1);
			}
			break;

		case LOOP_STATE_FOUND_START_CLOCKWISE:
			if (oil[left] - need >= 0)
			{
				++finishedCount;
				res[left] = true;
				foundSuitableStart = left;
				need = 0;
			}
			else
			{
				need -= oil[left];
			}

			left = (left == 0) ? last : (left - 1);

			break;

		default:
			assert(false);
			break;
		}
	}

	// 还原oil
	for (int i = 0; i < size; i++)
	{
		oil[i] = oil[i] + dis[i];
	}

	return res;
}

/**
 * N个加油站组成一个环形，给定两个长度都是N的非负数组oil和dis(N>1)，oil[i]代表第i个加油站存的油可以跑多少千米，dis[i]代表第i个加油站到环中下一个加油站相隔多少千米。
 * 假设你有一辆邮箱足够大的车，初始时车里没有油。如果车从第i个加油站触发，最终可以回到这个加油站，那么第i个加油站就算良好出发点，否则就不算。
 * 请返回长度为N的boolean型数组res，res[i]代表第i个加油站是不是良好出发点。
 * 
 * 思路：
 * 假设：
 * oil:  [3  2  1  4  2]
 * dis:  [4  1  3  2  1]
 * 
 *               3
 *           4  ←  1
 *          (3)    (2)
 *      2 ↙         ↖1
 *       2            2
 *      (4)  ↘1   4↗ (1)
 *               3
 *              (0)
 * 
 * 将oil数组加工成"纯能值"数组，即当前加油站的油，扣除它到下一站的距离，还剩下多少油.
 * oil:  [-1, 1, -2, 2, 1]
 * 功能实现完成之后，要记得将oil还原.
 * 原问题就变为 沿路途累加和是否小于0的问题了。
 * 所以，如果oil[i]是小于0的，那么它一定不是良好出发点。
 * 
 * 举例1:
 * 例子中为了防止oil[i]与i混淆，用26个字母替代i，作为索引
 * 
 * 
 * 2(G)←-2(F)←-1(E)←-3(D)←-3(C)   
 *	  ↘	     				  ↑
 *      5(H)→-4(I)→-2(A)→1(B)
 * 
 * 一开始从H出发, 设置一个连通区，[H,I), 左闭右开，表示一开始在H点还没有到I。
 * rest=5， 即H自己的值, 表示通过连通区之后，还剩多少油
 * need=0, 表示当前的节点要接到连通区的头上，至少需要多少油。
 * 
 * step1: 连通区的右边缘能否逆时针方向移动一格？
 * ∵I是-4，rest是5，∴可以右移，连通区变为[H,A), rest=5-4=1
 * 
 * step2: 连通区能否继续右移？
 * ∵A是-2，rest是1，∴无法继续右移，H不是良好出发点。
 * 
 * step3: 连通区能否左移一格，使得连通区变成[G,A)?
 * ∵目前need=0，G=2，∴可以左移。 这个时候，rest=3
 * 
 * step4：连通区能否右移一格，将联通区变为[G,B)?
 * ∵rest=3,A=-2,∴可以右移一格，连通区变为[G,B), rest=1
 * 
 * step5: 同理，连通区可以继续右扩，变为[G,C), rest=2
 * 
 * step6: C=-3，rest=2，无法继续右扩了，∴G也不是良好出发点.
 * 
 * step7: 连通区尝试左扩，F=-2，need=0，不满足扩的要求。∴F也不是良好出发点，need=2
 * 
 * step8: 连通区继续尝试左扩，E=-1，need=2，不满足扩的要求。∴E也不是良好出发点，need=3.
 * 
 * step9: 连通区继续尝试左扩，D=3，need=3，故满足扩的要求。need=0，连通区变为[D,C)
 * 
 * step10: 连通区能否右移一格? C=-3，rest=2，故无法右移，D也不是良好出发点
 * 
 * 至此，所有的点判断完毕:
 * res:[False,False,False,False,False,False,False,False,False]
 *        A     B     C     D     E     F     G     H     I
 * 
 * 举例2:
 * 例子中为了防止oil[i]与i混淆，用26个字母替代i，作为索引
 * 
 *     -1(G)←1(F)←-1(E)←-1(D)
 *    ↙                 ↗
 *   9(H)→3(A)→-4(B)→2(C)
 * 
 * 一开始从A出发，设置一个连通区[A,B), rest=3, need=0
 * step1: B=-4, rest=3, A到B无法右扩，只能左移， A不是良好出发点
 * 
 * step2: need=0, H=9, 故可以左扩，连通区[H,B), rest=12
 * 
 * step3: 右扩，连通区[H,C), rest=8
 * 
 * step4: 右扩，连通区[H,D), rest=10
 * 
 * step5: 右扩，连通区[H,E), rest=9
 * 
 * step6: 右扩，连通区[H,F), rest=8
 * 
 * step7: 右扩，连通区[H,G), rest=9
 * 
 * step8: 右扩，连通区[H,H), rest=8. 至此，H是良好出发点
 * 
 * 找到了一个良好出发点H之后，H之前的点如果能连入这个连通区，则它就是良好出发点
 * 
 * step9: 左扩，G=-1，无法到达H，G不是良好出发点，need=1
 * 
 * step10: 左扩，F=1，need=1，故可以到达H，F是良好出发点
 * 
 * 找到了一个良好出发点F之后，F之前的点如果能连入这个连通区，则它就是良好出发点。 need=0
 * 
 * step11: 左扩，E=-1，无法到达F，E不是良好出发点，need=1
 * 
 * step12: 左扩，D=-1, 无法到达F，D不是良好出发点，need=2
 * 
 * step13：左扩，C=2, need=2，故能到达F，C是良好出发点
 * 
 * 找到了一个良好出发点C之后，C之前的点如果能连入这个连通区，则它就是良好出发点。 need=0
 * 
 * step14：左扩，B=-4，无法到达C，B不是良好出发点，need=4
 * 
 * 至此，所有的点都判断完毕:
 * res:[False,False,True,False,False,True,False,True]
 *        A     B     C    D     E     F    G     H
 * 
 * 时间复杂度:O(N) 空间复杂度:O(1)
 */
int main_passAllPetrolStations()
{
	//int oil[] = { 3,2,1,4,2 };
	//int dis[] = { 4,1,3,2,1 };

	int oil[] = {4,2,5,4,6,8,4,12};
	int dis[] = {1,6,3,5,7,7,5,3};

	auto size = sizeof(oil) / sizeof(int);
	auto res = judgeSuitableStart(oil, dis, size);
	for (int i = 0; i < size; i++)
	{
		printf("res[%d]=%d\n", i, res[i]);
	}

	free(res);

	return 0;
}